<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>双端队列</title>
    </head>
    <body>
        <script>
            /**
             *  双端队列：是一种允许我们同时从前端和后端添加移除元素的特殊队列。
             *
             * */
            class Deque {
                constructor() {
                    this.count = 0;
                    this.lowestCount = 0;
                    this.items = {};
                }

                addFront(element) {
                    // 如果是空
                    if (this.isEmpty()) {
                        this.addBack(element);
                    } else if (this.lowestCount > 0) {
                        this.lowestCount--;
                        this.items[this.lowestCount] = element;
                    } else {
                        // 整体向右移动
                        for (let i = this.count; i > 0; i--) {
                            this.items[i] = this.items[i - 1];
                        }
                        this.count++;
                        this.lowestCount = 0;
                        this.items[0] = element;
                    }
                }

                addBack(element) {
                    this.items[this.count] = element;
                    this.count++;
                }

                removeFront() {
                    if (this.isEmpty()) {
                        return undefined;
                    }
                    const result = this.items[this.lowestCount];
                    delete this.items[this.lowestCount];
                    this.lowestCount++;
                    return result;
                }

                removeBack() {
                    if (this.isEmpty()) {
                        return undefined;
                    }
                    this.count--;
                    const result = this.items[this.count];
                    delete this.items[this.count];
                    return result;
                }

                peekFront() {
                    if (this.isEmpty()) {
                        return undefined;
                    }
                    return this.items[this.lowestCount];
                }

                peekBack() {
                    if (this.isEmpty()) {
                        return undefined;
                    }
                    return this.items[this.count - 1];
                }

                isEmpty() {
                    return this.size() === 0;
                }

                size() {
                    return this.count - this.lowestCount;
                }

                clear() {
                    this.items = {};
                    this.count = 0;
                    this.lowestCount = 0;
                }

                toString() {
                    if (this.isEmpty()) {
                        return "";
                    }
                    let objString = `${this.items[this.lowestCount]}`;
                    for (let i = this.lowestCount + 1; i < this.count; i++) {
                        objString = `${objString},${this.items[i]}`;
                    }
                    return objString;
                }
            }
        </script>
    </body>
</html>
